/**
 * 归并排序
 * 思想：将一个数组arr[q, r]拆分为两部分arr[q, p] arr[p + 1, r]
 * 然后分别对这两个小部分排序，最后在归并回来
 */

/* 

*/
function mergeArr(arr, left, q, right) {
  let tempArr = [];
  let leftIndex = left;
  let rightIndex = q + 1;
  let index = 0;
  while (leftIndex <= q && rightIndex <= right) {
    if (arr[leftIndex] < arr[rightIndex]) {
      tempArr[index++] = arr[leftIndex++];
    } else {
      tempArr[index++] = arr[rightIndex++];
    }
  }
  // 找出剩余的部分
  let start = leftIndex;
  let end = q;
  if (rightIndex <= right) {
    start = rightIndex;
    end = right;
  }
  while (start <= end) {
    tempArr[index++] = arr[start++];
  }

  // temp拷贝到arr
  for (let i = 0; i <= right - left; i++) {
    arr[left + i] = tempArr[i];
  }
}
function _mergeSort(arr, left, right) {
  if (left >= right) return;
  const centerIndex = Math.floor(left + (right - left) / 2);
  _mergeSort(arr, left, centerIndex);
  _mergeSort(arr, centerIndex + 1, right);
  mergeArr(arr, left, centerIndex, right);
}

function mergeSort(arr) {
  _mergeSort(arr, 0, arr.length - 1);
}

function test1() {
  const arr = [];
  let i = 0;
  while (i < 10) {
    arr.push(Math.floor(Math.random() * 100));
    i++;
  }
  console.log(arr);
  console.log('------');
  mergeSort(arr);
  console.log(arr);
}
// test1();
function test2() {
  function mergeArr(arr, left, centerIndex, right) {
    let leftIndex = left;
    let rightIndex = centerIndex + 1;
    let tempArr = [];
    while (leftIndex <= centerIndex && rightIndex <= right) {
      if (arr[leftIndex] < arr[rightIndex]) {
        tempArr.push(arr[leftIndex]);
        leftIndex++;
      } else {
        tempArr.push(arr[rightIndex]);
        rightIndex++;
      }
    }

    // 找出剩余的部分
    let start = leftIndex;
    let end = centerIndex;
    if (rightIndex <= right) {
      start = rightIndex;
      end = right;
    }
    while (start <= end) {
      tempArr.push(arr[start++]);
    }
    for (let i = 0; i <= right - left; i++) {
      arr[left + i] = tempArr[i];
    }
  }
  function _mergeSort(arr, left, right) {
    if (left >= right) return;
    const centerIndex = Math.floor((left + right) / 2);
    _mergeSort(arr, left, centerIndex);
    _mergeSort(arr, centerIndex + 1, right);
    // 排序好之后，将左右已经排序好的数组合并到arr内
    mergeArr(arr, left, centerIndex, right);
  }
  function mergeSort(arr) {
    _mergeSort(arr, 0, arr.length - 1);
  }

  const arr = [];
  let i = 0;
  while (i < 10) {
    arr.push(Math.floor(Math.random() * 100));
    i++;
  }
  console.log(arr);
  console.log('------');
  mergeSort(arr);
  console.log(arr);
}

test2();
[].sort();